package main

import "fmt"

// 如何求正整数 n 所有可能的整数组合

func main() {
	showAllCombination(4)
}

func getAllCombination(sum int, result []int, count int) {
	// 如果数字的组合满足和为 sum，打印出所有组合
	if sum == 0 {
		for i := 0; i < count; i++ {
			fmt.Print(result[i], " ")
		}
		fmt.Println()
		return
	}

	// 确定组合的下一个取值，保证 next 的值不低于 result 中最大的一个
	var next int
	if count == 0 {
		next = 1
	} else {
		next = result[count-1]
	}

	// 尝试填入值
	for i := next; i <= sum; i++ {
		result[count] = i
		count++
		getAllCombination(sum-i, result, count)
		count--
	}
}

func showAllCombination(n int) {
	if n < 1 {
		return
	}
	result := make([]int, n)
	getAllCombination(n, result, 0)
}
